package com.taotao.linklist;

import lombok.Getter;
import lombok.Setter;

import java.util.Objects;

/**
 * 单向链表
 *
 * @author youbeiwuhuan
 * @date 2020/7/8 21:43
 */
@Getter
public class SingleLinkedList<T> {
    /**
     * 链表节点
     */
    @Getter
    @Setter
    public static class Node<T> {
        T data;
        Node<T> next;
    }


    /**
     * 链表头节点
     */
    private Node<T> head;


    public SingleLinkedList() {
        this.head = new Node<>();
    }


    /**
     * 判断链表是否有环
     *
     * @return
     */
    public boolean hasLoop() {
        return false;
    }


    /**
     * 获取链表中节点
     *
     * @return
     */
    public Node<T> getMidNode() {

        Node<T> fastP = head;
        Node<T> slowP = head;

        while (fastP != null && null != fastP.next) {
            fastP = fastP.next.next;
            slowP = slowP.next;
        }


        return slowP;
    }

    /**
     * 获取倒数第n个节点
     *
     * @param n
     * @return
     */
    public Node<T> getLastNNode(int n) {
        Node<T> fastP = head;
        Node<T> slowP = head;

        //fastP先走n步
        int i = 0;
        while (i < n && null != fastP.next) {
            fastP = fastP.next;
            i++;
        }

        while (null != fastP.next) {
            fastP = fastP.next;
            slowP = slowP.next;
        }


        return slowP;
    }


    /**
     * 追加元素
     *
     * @param data
     */
    public void append(T data) {
        if (null == data) {
            return;
        }

        Node<T> lastNode = head;
        while (null != lastNode.next) {
            lastNode = lastNode.next;
        }

        Node<T> node = new Node<>();
        node.setData(data);
        lastNode.next = node;
    }


    public void remove(T data) {
        if (null == data) {
            throw new IllegalArgumentException();
        }

        //find the target node
        Node<T> prev = head;
        Node<T> cur = prev.next;
        while (null != cur && !Objects.equals(cur.data, data)) {
            cur = cur.next;
        }

        //remove
        prev.next = cur.next;
    }


    /**
     * 反转链表
     */
    public void reverse() {
        /**
         * 断开旧头结点，把链表中节点一个个插到旧头节点后
         */


        Node<T> nextNode = head.next;
        //断开旧头结点,这里不断开会造成翻转后尾节点自己成环
        head.next = null;

        while (null != nextNode) {
            Node<T> nextNode0 = nextNode;
            nextNode = nextNode.next;

            //把节点插到旧节点后面
            nextNode0.next = head.next;
            head.next = nextNode0;
        }

    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("head");
        Node<T> nextNode = head.next;
        while (null != nextNode) {
            sb.append(" -> ").append(nextNode.data);
            nextNode = nextNode.next;
        }

        return sb.toString();
    }
}
